质因数

Posted on | Post modified: | In |
Words count in article: 755

质因数判定（试除法）

一个数可质因子分解为两个数相乘，假设$d$为$n$的较小的那个质因子，则满足 $d \le \frac n d$，即$d \le \sqrt n$。因此用试除法枚举质因子时只需要枚举到根号n即可。

1
2
3
4
5
6
7
bool prim(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= n / i; ++ i) {  // i < n / i  ==   i < sqrt(n) 且速度较快
        if (n % i == 0) return false;
    }
    return true;
}

质因子分解（试除法）

一个合数可分解为若干个质数的乘积，在分解时不仅需要让因子的乘积为该合数，还需要保证它们是质数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int divide(int n) {
    for (int i = 2; i <= n / i; ++ i) {
        
        if (n % i == 0) {  // 找到一个质因子
            int cnt = 0;
            while (n % i == 0) {  // 判断可被该质因子除多少次
                n /= i;
                ++ cnt;
            }
            cout << i << ' ' << cnt << endl;
        }
    }
    
    if (n > 1) cout << n << ' ' << 1 << endl;  // n未被除完则剩余一个大于根号n的质因子
    puts("");
}

质数筛选

判断1~n中质数的数量，区别与判断一个数是否是质数，需要将1~n范围内的所有质数求出来，因此可以利用之前已求得的质数对后面的数进行筛选，而不是挨个用试除法进行判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int prime[N], cnt;
bool st[N];

// 朴素筛选，O(nlogn)
void get_primes(int n) {
    for (int i = 2; i <= n; ++ i) {
        if (!st[i]) prime[cnt ++ ] = i;  // 保存该质数
        for (int j = i + i; j <= n; j += i) st[j] = true;  // 根据该当前数筛选后面的合数， 该数的倍数都是合数（k * i) 
    }
}


// 埃式筛选 O(nloglogn)
void get_prime(int n) {
    for (int i = 2; i <= n; ++ i) {
        if (!st[i]) {
            prime[cnt ++] = i;
            for (int j = i + i; j <= n; j += i) st[j] = true;  // 直接根据质数筛选，避免重复
        }
    }
}

// 线性筛  ，原理：只用最小质因子筛选合数，这样每个合数只会被筛一次。
void get_primeline(int n) {
    for (int i = 2; i <= n; ++ i) {
        if (!st[i]) prime[cnt ++] = i;  // 记录质数
        
        for (int j = 0; prime[j] <=  n / i; ++ j) {  // 右边界是 n / i，因为需要prime[j] * i  。    从小到大枚举质因子
            st[prime[j] * i] = true;          // prime[j] 是 prime[j] * i 的最小质因子 
            if (i % prime[j] == 0)  break;    // 当prime[j]是i的质因子后退出，避免重复筛选
        }
    }
    
}

快速幂

假设$k$为6，那么 $k$ 可按二进制分解为110 ，进一步$a^k$可分解为

其实就是按k的二进制，其中二进制位为1的时候，就可以与答案乘起来，并且由于每一项是按平方增长的，因此下一项可以直接用上一项的求平方。

1
2
3
4
5
6
7
8
9
int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a;
        a = a * a;
        k >>= 1;
    }
    return res;
}

未考虑溢出